package top.hkyzf.study.leetcode.graph;

import org.junit.Test;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

/**
 * @author 朱峰
 * @date 2022-1-25 11:53
 */
public class 图像渲染_733 {
    /**
     * 广度优先（队列）
     */
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int oldColor = image[sr][sc];
        if (oldColor == newColor) {
            return image;
        }
        Queue<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{sr, sc});
        while (!queue.isEmpty()) {
            int[] point = queue.poll();
            image[point[0]][point[1]] = newColor;

            int[] pointUp = new int[]{point[0]-1, point[1]};
            int[] pointDown = new int[]{point[0]+1, point[1]};
            int[] pointLeft = new int[]{point[0], point[1]-1};
            int[] pointRight = new int[]{point[0], point[1]+1};
            if (pointUp[0] >= 0 && image[pointUp[0]][pointUp[1]] == oldColor) {
                queue.offer(pointUp);
            }
            if (pointDown[0] < image.length && image[pointDown[0]][pointDown[1]] == oldColor) {
                queue.offer(pointDown);
            }
            if (pointLeft[1] >= 0 && image[pointLeft[0]][pointLeft[1]] == oldColor) {
                queue.offer(pointLeft);
            }
            if (pointRight[1] < image[0].length && image[pointRight[0]][pointRight[1]] == oldColor) {
                queue.offer(pointRight);
            }
        }
        return image;
    }

    /**
     * 深度优先（递归）
     */
    public int[][] floodFillDfs(int[][] image, int sr, int sc, int newColor) {
        int oldColer = image[sr][sc];
        if(oldColer != newColor) {
            dfs(image, sr, sc, oldColer, newColor);
        }
        return image;
    }

    void dfs (int[][] image, int sr, int sc, int oldColor, int newColor) {
        if (image[sr][sc] == oldColor) {
            image[sr][sc] = newColor;
            // 上
            if (sc-1 >=0) {
                dfs(image, sr, sc-1, oldColor, newColor);
            }
            // 下
            if (sc+1 < image.length) {
                dfs(image, sr, sc+1, oldColor, newColor);
            }
            // 左
            if (sr-1 >= 0) {
                dfs(image, sr-1, sc, oldColor, newColor);
            }
            // 右
            if (sr+1 < image[0].length) {
                dfs(image, sr+1, sc, oldColor, newColor);
            }
        }
    }

    @Test
    public void testFloodFill () {
        int[][] image = {{1,1,1},{1,1,0},{1,0,1}};
        int sr = 1, sc = 1;
        int newColor = 2;
        int[][] floodFill = floodFillDfs(image, sr, sc, newColor);
        for (int[] ints : floodFill) {
            System.out.println(Arrays.toString(ints));
        }
    }
}
